package org.cabbage.lintcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 扔 n 个骰子，向上面的数字之和为 S。给定 Given n，请列出所有可能的 S 值及其相应的概率。
 *
 * @author gezhangyuan
 */
public class DicesSumV2 {

    static long t = 0;

    public static void main(String[] args) {
        List<Map.Entry<Integer, Double>> result = dicesSum(15);
        result.forEach((e) -> {
            System.out.println(e.getKey() + ":" + e.getValue());
            t += e.getValue();
        });
        System.out.println(t);
        System.out.println(Math.pow(6, 15));
    }

    public static List<Map.Entry<Integer, Double>> dicesSum(int n) {
        long[] t1 = null;
        long[] t2 = new long[7];
        for (int i = 1; i <= 6; i++) {
            t2[i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            t1 = t2;
            t2 = new long[6 * i + 1];
            for (int j = i; j <= 6 * i; j++) {
                long sum = 0;
                for (int k = 1; k < 7; k++) {
                    if (j - k > 0 && j - k <= 6 * (i - 1)) {
                        sum += t1[j - k];
                    }
                }
                t2[j] = sum;
            }
        }

        Map<Integer, Double> r = new HashMap<Integer, Double>();
        double count = Math.pow(6, n);
        for (int i = n; i <= 6 * n; i++) {
            r.put(i, t2[i] / count);
        }
        return new ArrayList<Map.Entry<Integer, Double>>(r.entrySet());
    }
}
